// Implementation of Dijkstra and Kruskal Algorithms
// Vertices are labled with integers starting with 0

#include <vector>
#include <list>
#include <set>
#include <limits>

#include <iostream>

using namespace std;


typedef int vertex_t;
typedef double weight_t;
struct neighbor {
	vertex_t target;
	weight_t weight;
	neighbor(vertex_t t, weight_t w)
		: target(t), weight(w) { }
};
typedef vector < vector < neighbor > > adjacency_list_t;
const weight_t max_weight = numeric_limits<double>::infinity();
typedef int priority_t;

class Graph {
	int v; // Number of vertices
	int e; // Number of edges
	adjacency_list_t adj; // The adjacency list

public:
	// Consruct a graph of with n vertices
	Graph(int n)
	{
		v = n;
		e = 0;
		adj.resize(n);
	}

	// Returns the number of vertices in the graph
	int V()
	{
		return v;
	}

	//Returns the number of edges in the graph
	int E()
	{
		return e;
	}

	// tests whether there is an edge from node x to node y.
	bool adjacent(vertex_t x, vertex_t y)
	{
		for(vector<neighbor>::iterator it = adj[x].begin();
				it != adj[x].end();
				it++) {

			if(it->target == y) return true;
		}
		return false;
	}

	// lists all neighbors y such that there is an edge from x to y.
	vector<neighbor> getNeighbors(vertex_t x)
	{
		return adj[x];
	}

	// adds to G the edge from x to y with weight w, if it is not there.
	void addEdge(vertex_t x, vertex_t y, weight_t w)
	{
		//adj[x].resize(adj[x].size() + 1);
		adj[x].push_back(neighbor(y, w));
		e++;
	} // TODO check for when the edge already exists

	// removes the edge from x to y, if it is there.
	void deleteEdge(vertex_t x, vertex_t y)
	{
		adj[x].erase(adj[x].begin()+y);
		e--;
	} // TODO check for when edge doesn't exist

/*
	// returns the value associated with the node x.
	int get_node_value (Graph &G, vertex_t x)
	{
		return static_cast<int>(x);
	}

	// sets the value associated with the node x to a.
	void set_node_value(Graph &G, vertex_t x, int a)
	{
	}
*/
	// returns the weight associated to the edge (x,y).
	// If there is not edge between x and y return 0
	weight_t getWeight(vertex_t x, vertex_t y)
	{
		for (vector<neighbor>::iterator it = adj[x].begin();
				it != adj[x].end();
				it++) {
			if(it->target == y) return it->weight;
		}
		return 0;
	}

	// sets the weight associated to the edge (x,y) to w.
	void setWeight(vertex_t x, vertex_t y, weight_t w)
	{
		for (vector<neighbor>::iterator it = adj[x].begin();
				it != adj[x].end();
				it++) {
			if(it->target == y){
				it->weight = w;
			}
		}
	}
	
};

// Using a std::set as a priority queue
template <class T>
class PriorityQueue {
	set<T> s;

public:
	// changes the priority (node value) of queue element.
	void changePrioirity(priority_t priority)
	{
	}

	// removes the top element of the queue.
	T minPriority()
	{
		T elem = *s.begin();
		s.erase(s.begin());
		return elem;
	}

	// does the queue contain queue_element.
	bool contains(T queueElement)
	{
		if (*s.find(queueElement)) return true;
		return false;
	}

	// insert queue_element into queue
	void insert(T queueElement)
	{
		s.insert(queueElement);
	}

	// returns the top element of the queue.
	T top()
	{
		return *(s.begin());
	}

	// return the number of queue_elements.
	int size()
	{
		return s.size();
	}

	void print() {
		while(!s.empty()) {
			cout << *(s.begin()) << endl;
			s.erase(s.begin());
		}
	}
};

class ShortestPathAlgo {

public:
	// List of vertices in G(V,E).
	list<vertex_t> vertices(Graph &graph)
	{
	}

	// Find shortest path between u-w and returns the sequence of vertices
	//+representing shorest path u-v1-v2-…-vn-w.
	list<vertex_t> path(Graph &graph, vertex_t u, vertex_t w)
	{
	}

	// return the path cost associated with the shortest path
	weight_t path_size(Graph &graph, vertex_t u, vertex_t v)
	{
		return 0;
	}
};

void testGraph() {
	Graph g(10);
	g.addEdge(0, 1, 5);
	g.addEdge(0, 2, 4);
	g.addEdge(1, 0, 5);
	g.addEdge(2, 0, 4);
	cout << "V(): " << g.V() << endl;
	cout << "E(): " << g.E() << endl;
	cout << "Adjacent(0, 1)? :" << g.adjacent(0, 1) << endl;
	cout << "Neighbors of 0: " << endl;
	for (vector<neighbor>::const_iterator it = g.getNeighbors(0).begin();
			it != g.getNeighbors(0).end();
			it++) {
		cout << "t: " << it->target << "; w: " << it->weight << endl;
	}
	cout << "getWeight(0, 1): " << g.getWeight(0, 1) << endl;
	g.setWeight(0, 1, 10);
	cout << "getWeight(0, 1) after setWeight(0,1,10): " << g.getWeight(0, 1) << endl;

}

void testQ()
{
	PriorityQueue<int> q;
	q.insert(1);
	q.insert(2);
	q.insert(5);
	q.insert(0);
	cout << "Top: " << q.top() << endl;
	cout << "minPriority: " << q.minPriority() << endl;
	q.print();
	//if (q.contains(1)) cout << "Contains 5" << endl;
	//else cout << "not found 5" << endl;
}

// TODO comparable
class Edge {
	vertex_t u;
	vertex_t v;
	weight_t w;
public:
	
}; 

class Kruskal {
	PriorityQueue<Edge> mst;
	weight_t weight;

public:
	
};


int main(void)
{
	testQ();
	//testGraph();

	/*
	adj[0].push_back(neighbor(1, 7));
	adj[0].push_back(neighbor(2, 9));
	adj[0].push_back(neighbor(5, 14));

	adj[1].push_back(neighbor(0, 7));
	adj[1].push_back(neighbor(2, 10));
	adj[1].push_back(neighbor(3, 15));

	adj[2].push_back(neighbor(1, 10));
	adj[2].push_back(neighbor(3, 11));
	adj[2].push_back(neighbor(5, 2));

	adj[3].push_back(neighbor(2, 11));
	adj[3].push_back(neighbor(1, 15));
	adj[3].push_back(neighbor(4, 6));

	adj[4].push_back(neighbor(3, 6));
	adj[4].push_back(neighbor(5, 9));

	adj[5].push_back(neighbor(4, 9));
	adj[5].push_back(neighbor(2, 2));
	adj[5].push_back(neighbor(0, 14));
	*/

	return 0;
}
